"""
全局最近邻点匹配
"""
import copy
import time
import CNM
import math_utility as mu


GLOBAL_SEQ = []
GLOBAL_SUM = []


# 判断是否已经被选择
def inline(seq, layer, n):
    for i in range(layer):
        if seq[i] == n:
            return True
    return False


# 深搜
def search(table, layer, cache_seq, cache_sum, optimize):
    for i in range(len(table)):
        if not inline(cache_seq, layer, i):
            cache_seq[layer] = i
            cache_sum += table[i][layer]
            copy_seq = copy.deepcopy(cache_seq)     # 深拷贝，不然每次拿到的只是seq的引用
            if layer == len(table[0]) - 1:
                GLOBAL_SEQ.append(copy_seq)
                GLOBAL_SUM.append(cache_sum)
            else:
                search(table, layer + 1, copy_seq, cache_sum, optimize)
            cache_sum -= table[i][layer]


# 全局最近邻点匹配
def point_matching(can, tar):
    exchange = False
    # 计算匹配后的序列长度
    if len(can) > 10 or len(tar) > 10:
        raise ValueError("The length of list can't more than 10!")
    if len(can) < len(tar):
        exchange = True
        temp = can
        can = tar
        tar = temp
    # 获取距离表
    table = [[0] * len(tar) for i in range(len(can))]
    for i in range(len(can)):
        for j in range(len(tar)):
            table[i][j] = round(mu.get_distance(can[i], tar[j]), 1)
    # 递归搜索全部解集
    seq = [None for i in range(len(table[0]))]
    optimize = []
    search(table, 0, seq, 0, optimize)
    # 获取解集中的最优解（距离最小）
    min_value = 10000
    min_index = 0
    for i in range(len(GLOBAL_SUM)):
        if GLOBAL_SUM[i] < min_value:
            min_value = GLOBAL_SUM[i]
            min_index = i
    # 总是让较小的序列成为can
    match = []
    if exchange:
        for i in range(len(GLOBAL_SEQ[min_index])):
            match.append([i, GLOBAL_SEQ[min_index][i]])
    else:
        for i in range(len(GLOBAL_SEQ[min_index])):
            match.append([GLOBAL_SEQ[min_index][i], i])
    return match


if __name__ == '__main__':
    can = [[0, 2], [1, 1], [3, 1], [4, 2], [5, 3], [7, 7]]
    tar = [[1, 2], [3, 2], [4, 3], [5, 4], [6, 5]]

    sta = time.time()
    print('GNNM: ', point_matching(can, tar))
    end = time.time()
    print('GNNM TIME: ', end - sta)

    sta = time.time()
    print('CNM: ', CNM.point_matching(can, tar))
    end = time.time()
    print('CNM TIME: ', end - sta)
